• The left subtree of a node contains only nodes with keys lesser than or equal to the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• The left and right subtree each must also be a binary search tree.
  There must be no duplicate nodes.

Searching a Key

1. Start from root.
2. Compare the key element with root, if less than root, then recur for left subtree, else recur for right subtree.
3. If element to search is found anywhere, return true, else return false.

Step 1: Compare 6 with 8.
        Since 6 is less than 8, 
        move to left subtree.
Step 2: Compare 6 with 3.
        Since 6 is greater than 3, 
        move to its right subtree.
Step 3: Comapre 6 with 6.
        Node Found.

Insertion of a Key

         100                               100
        /   \        Insert 40            /    \
      20     500    --------->          20     500 
     /  \                              /  \  
    10   30                           10   30
                                              \   
                                              40

// C++ program to demonstrate insert 
// operation in binary search tree

#include<bits/stdc++.h>
using namespace std;

// Binary Search Tree node
struct node
{
    int key;
    struct node *left, *right;
};

// A utility function to create a new BST node
struct node *newNode(int item)
{
    node *temp = new node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        cout<<root->key<<" ";
        inorder(root->right);
    }
}

// A utility function to insert a new node 
// with given key in BST 
struct node* insert(struct node* node, int key)
{
    /* If the tree is empty, return a new node */
    if (node == NULL) return newNode(key);

    /* Otherwise, recur down the tree */
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key); 

    /* return the (unchanged) node pointer */
    return node;
}

// Driver Program to test above functions
int main()
{
    /* Let us create following BST
          50
        /     \
       30     70
      / \    / \
     20 40  60 80 */
    struct node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    // print inoder traversal of the BST
    inorder(root);

    return 0;
}

// Java program to demonstrate insert 
// operation in binary search tree

class BinarySearchTree {

    /* Class containing left and right
       child of current node and key value */
    class Node {
        int key;
        Node left, right;

        public Node(int item) {
            key = item;
            left = right = null;
        }
    }

    // Root of BST
    Node root;

    // Constructor
    BinarySearchTree() { 
        root = null; 
    }

    // This method mainly calls insertRec()
    void insert(int key) {
       root = insertRec(root, key);
    }
    
    /* A recursive function to insert a new key in BST */
    Node insertRec(Node root, int key) {

        /* If the tree is empty, return a new node */
        if (root == null) {
            root = new Node(key);
            return root;
        }

        /* Otherwise, recur down the tree */
        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);

        /* return the (unchanged) node pointer */
        return root;
    }

    // This method mainly calls inorderRec()
    void inorder() {
        inorderRec(root);
    }

    // A utility function to do inorder traversal of BST
    void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);

            System.out.print(root.key+" ");
            
            inorderRec(root.right);
        }
    }

    // Driver Code
    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();

        /* Let us create following BST
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        // print inorder traversal of the BST
        tree.inorder();
    }
}

20 30 40 50 60 70 80

1. Start from root.
2. Compare the element to be inserted with root, if it is less than root, then recur for left-subtree, else recur for right-subtree.
3. After reaching end,just insert that node at left(if less than current leaf node) else right.

Element to be inserted: 2

Step 1: Compare 2 with 8.
        Since 2 is less than 8, 
        move to left subtree.
Step 2: Compare 2 with 3.
        Since 2 is less than 3, 
        move to its left subtree.
Step 3: Comapre 2 with 1.
        Since 2 is greater than 1 and also 1 is a leaf node.
        Insert 2 as its right child of node 1.

1. Node to be deleted is leaf: Simply remove from the tree.

2. Node to be deleted has only one child: Copy the child to the node and delete the child.

3. Node to be deleted has two children: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
   

// C++ program to demonstrate delete 
// operation in binary search tree
#include<bits/stdc++.h>
using namespace std;

// BST Node
struct node
{
    int key;
    struct node *left, *right;
};

// A utility function to create a new BST node
struct node *newNode(int item)
{
    node *temp = new node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        cout<<root->key<<" ";
        inorder(root->right);
    }
}

// A utility function to insert a new node 
// with given key in BST 
struct node* insert(struct node* node, int key)
{
    // If the tree is empty, return a new node 
    if (node == NULL) 
        return newNode(key);

    // Otherwise, recur down the tree 
    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);

    // return the (unchanged) node pointer 
    return node;
}

// Function to find the minimum
// valued node in a BST
struct node * minValueNode(struct node* node)
{
    struct node* current = node;

    /* loop down to find the leftmost leaf */
    while (current->left != NULL)
        current = current->left;

    return current;
}

// Function to delete a given node from the BST
struct node* deleteNode(struct node* root, int key)
{
    // base case
    if (root == NULL) return root;

    // If the key to be deleted is smaller than the root's key,
    // then it lies in left subtree
    if (key < root->key)
        root->left = deleteNode(root->left, key);

    // If the key to be deleted is greater than the root's key,
    // then it lies in right subtree
    else if (key > root->key)
        root->right = deleteNode(root->right, key);

    // if key is same as root's key, then This is the node
    // to be deleted
    else
    {
        // node with only one child or no child
        if (root->left == NULL)
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }

        // node with two children: Get the inorder successor (smallest
        // in the right subtree)
        struct node* temp = minValueNode(root->right);

        // Copy the inorder successor's content to this node
        root->key = temp->key;

        // Delete the inorder successor
        root->right = deleteNode(root->right, temp->key);
    }
    
    return root;
}

// Driver Program to test above functions
int main()
{
    /* Let us create following BST
          50
        /     \
       30     70
      /  \   / \
     20  40 60  80 */
    struct node *root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);

    cout<<"Inorder traversal of the given tree \n";
    inorder(root);

    cout<<"\nDelete 20\n";
    root = deleteNode(root, 20);
    cout<<"Inorder traversal of the modified tree \n";
    inorder(root);

    cout<<"\nDelete 30\n";
    root = deleteNode(root, 30);
    cout<<"Inorder traversal of the modified tree \n";
    inorder(root);

    cout<<"\nDelete 50\n";
    root = deleteNode(root, 50);
    cout<<"Inorder traversal of the modified tree \n";
    inorder(root);

    return 0;
}

// Java program to demonstrate delete 
// operation in binary search tree

class BinarySearchTree
{
    /* Class containing left and right child of current node and key value*/
    class Node
    {
        int key;
        Node left, right;

        public Node(int item)
        {
            key = item;
            left = right = null;
        }
    }

    // Root of BST
    Node root;

    // Constructor
    BinarySearchTree()
    {
        root = null;
    }

    // This method mainly calls deleteRec()
    void deleteKey(int key)
    {
        root = deleteRec(root, key);
    }

    /* A recursive function to insert a new key in BST */
    Node deleteRec(Node root, int key)
    {
        /* Base Case: If the tree is empty */
        if (root == null)  return root;

        /* Otherwise, recur down the tree */
        if (key < root.key)
            root.left = deleteRec(root.left, key);
        else if (key > root.key)
            root.right = deleteRec(root.right, key);

        // if key is same as root's key, then This is the node
        // to be deleted
        else
        {
            // node with only one child or no child
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;

            // node with two children: Get the inorder successor (smallest
            // in the right subtree)
            root.key = minValue(root.right);

            // Delete the inorder successor
            root.right = deleteRec(root.right, root.key);
        }

        return root;
    }

    int minValue(Node root)
    {
        int minv = root.key;
        while (root.left != null)
        {
            minv = root.left.key;
            root = root.left;
        }
        return minv;
    }

    // This method mainly calls insertRec()
    void insert(int key)
    {
        root = insertRec(root, key);
    }

    /* A recursive function to insert a new key in BST */
    Node insertRec(Node root, int key)
    {

        /* If the tree is empty, return a new node */
        if (root == null)
        {
            root = new Node(key);
            return root;
        }

        /* Otherwise, recur down the tree */
        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);

        /* return the (unchanged) node pointer */
        return root;
    }

    // This method mainly calls InorderRec()
    void inorder()
    {
        inorderRec(root);
    }

    // A utility function to do inorder traversal of BST
    void inorderRec(Node root)
    {
        if (root != null)
        {
            inorderRec(root.left);
            System.out.print(root.key + " ");
            inorderRec(root.right);
        }
    }

    // Driver Program to test above functions
    public static void main(String[] args)
    {
        BinarySearchTree tree = new BinarySearchTree();

        /* Let us create following BST
              50
           /     \
          30      70
         /  \    /  \
        20   40  60   80 */
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        System.out.println("Inorder traversal of the given tree");
        tree.inorder();

        System.out.println("\nDelete 20");
        tree.deleteKey(20);
        System.out.println("Inorder traversal of the modified tree");
        tree.inorder();

        System.out.println("\nDelete 30");
        tree.deleteKey(30);
        System.out.println("Inorder traversal of the modified tree");
        tree.inorder();

        System.out.println("\nDelete 50");
        tree.deleteKey(50);
        System.out.println("Inorder traversal of the modified tree");
        tree.inorder();
    }
}

Inorder traversal of the given tree
20 30 40 50 60 70 80
Delete 20
Inorder traversal of the modified tree
30 40 50 60 70 80
Delete 30
Inorder traversal of the modified tree
40 50 60 70 80
Delete 50
Inorder traversal of the modified tree
40 60 70 80

LCA of 10 and 14 is 12
LCA of 14 and 8 is 8
LCA of 10 and 22 is 20

The LCA or Lowest Common Ancestor of any two nodes N1 and N2 is defined as the common ancestor of both the nodes which is closest to them. That is the distance of the common ancestor from the nodes N1 and N2 should be least possible.

Finding LCA

// A recursive CPP program to find
// LCA of two nodes n1 and n2.

#include <bits/stdc++.h>
using namespace std;

class node 
{ 
    public:
    int data; 
    node* left, *right; 
}; 

// Function to find LCA of n1 and n2. 
// The function assumes that both 
// n1 and n2 are present in BST 
node *lca(node* root, int n1, int n2) 
{ 
    if (root == NULL) return NULL; 

    // If both n1 and n2 are smaller
    // than root, then LCA lies in left 
    if (root->data > n1 && root->data > n2) 
        return lca(root->left, n1, n2); 

    // If both n1 and n2 are greater than 
    // root, then LCA lies in right 
    if (root->data < n1 && root->data < n2) 
        return lca(root->right, n1, n2); 

    return root; 
} 

// Helper function that allocates 
// a new node with the given data.
node* newNode(int data) 
{ 
    node* Node = new node();
    Node->data = data; 
    Node->left = Node->right = NULL; 
    return(Node); 
} 

// Driver Code 
int main() 
{ 
    // Let us construct the BST 
    // shown in the above figure 
    node *root = newNode(20); 
    root->left = newNode(8); 
    root->right = newNode(22); 
    root->left->left = newNode(4); 
    root->left->right = newNode(12); 
    root->left->right->left = newNode(10); 
    root->left->right->right = newNode(14); 

    int n1 = 10, n2 = 14; 
    node *t = lca(root, n1, n2); 
    cout << "LCA of " << n1 << " and " << n2 
         << " is " << t->data<<endl; 

    n1 = 14, n2 = 8; 
    t = lca(root, n1, n2); 
    cout<<"LCA of " << n1 << " and " << n2 
        << " is " << t->data << endl; 

    n1 = 10, n2 = 22; 
    t = lca(root, n1, n2); 
    cout << "LCA of " << n1 << " and " << n2 
         << " is " << t->data << endl; 

    return 0; 
} 

// Recursive Java program to print lca of two nodes

// A binary tree node
class Node 
{
    int data;
    Node left, right;

    Node(int item) 
    {
        data = item;
        left = right = null;
    }
}

class BinaryTree 
{
    Node root;
    
    /* Function to find LCA of n1 and n2. 
       The function assumes that both
       n1 and n2 are present in BST */
    Node lca(Node node, int n1, int n2) 
    {
        if (node == null)
            return null;

        // If both n1 and n2 are smaller than root, 
        // then LCA lies in left subtree
        if (node.data > n1 && node.data > n2)
            return lca(node.left, n1, n2);

        // If both n1 and n2 are greater than root,
        // then LCA lies in right subtree
        if (node.data < n1 && node.data < n2) 
            return lca(node.right, n1, n2);

        return node;
    }

    // Driver Code
    public static void main(String args[]) 
    {
        // Let us construct the BST shown
        // in the above figure
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(20);
        tree.root.left = new Node(8);
        tree.root.right = new Node(22);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(12);
        tree.root.left.right.left = new Node(10);
        tree.root.left.right.right = new Node(14);

        int n1 = 10, n2 = 14;
        Node t = tree.lca(tree.root, n1, n2);
        System.out.println("LCA of " + n1 + " and " 
                               + n2 + " is " + t.data);

        n1 = 14;
        n2 = 8;
        t = tree.lca(tree.root, n1, n2);
        System.out.println("LCA of " + n1 + " and " 
                                + n2 + " is " + t.data);

        n1 = 10;
        n2 = 22;
        t = tree.lca(tree.root, n1, n2);
        System.out.println("LCA of " + n1 + " and " 
                                + n2 + " is " + t.data);

    }
}

LCA of 10 and 14 is 12
LCA of 14 and 8 is 8
LCA of 10 and 22 is 20

Why AVL Trees?

Insertion

1. Left Rotation
2. Right Rotation

T1, T2 and T3 are subtrees of the tree 
rooted with y (on the left side) or x (on 
the right side)        

Keys in both of the above trees follow the 
following order: 
 keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)

So BST property is not violated anywhere.

1. Perform standard BST insert for w.
2. Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced node, y be the child of z that comes on the path from w to z and x be the grandchild of z that comes on the path from w to z.
3. Re-balance the tree by performing appropriate rotations on the subtree rooted with z. There can be 4 possible cases that need to be handled as x, y and z can be arranged in 4 ways. Following are the possible 4 arrangements:
   
   • y is left child of z and x is left child of y (Left Left Case)
   • y is left child of z and x is right child of y (Left Right Case)
   • y is right child of z and x is right child of y (Right Right Case)
   • y is right child of z and x is left child of y (Right Left Case)

T1, T2, T3 and T4 are subtrees.